package com.sicheng.lc.周赛.分类.dp.计数;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/26 22:44
 */
public class 统计打字方案数 {
    //https://leetcode.cn/problems/count-number-of-texts/

    static int[] map = {0, 0, 3, 3, 3, 3, 3, 4, 3, 4};
    static int[] dp3 = new int[(int) (1e5 + 1)];
    static int[] dp4 = new int[(int) (1e5 + 1)];
    static int mod = (int) (1e9 + 7);

    public int countTexts(String pressedKeys) {
        init();
        int last = 0;
        long res = 1;
        for (int i = 0; i < pressedKeys.length(); i++) {
            while (i < pressedKeys.length() && pressedKeys.charAt(i) == pressedKeys.charAt(last)) {
                i++;
            }
            res = res * get(pressedKeys.charAt(last) - '0', i - last) % mod;
            last = i;
        }
        if (last < pressedKeys.length()) {
            res = res * get(pressedKeys.charAt(last) - '0', pressedKeys.length() - last) % mod;
        }

        return (int) res;
    }

    private void init() {
        dp3[0] = 1;
        dp3[1] = 1;
        dp3[2] = 2;

        dp4[0] = 1;
        dp4[1] = 1;
        dp4[2] = 2;
        dp4[3] = 4;
        for (int i = 3; i < dp3.length; i++) {
            dp3[i] = ((dp3[i - 1] + dp3[i - 2]) % mod + dp3[i - 3]) % mod;
        }
        for (int i = 4; i < dp4.length; i++) {
            dp4[i] = (((dp4[i - 1] + dp4[i - 2]) % mod + dp4[i - 3]) % mod + dp4[i - 4]) % mod;
        }
    }

    public long get(int ch, int len) {
        return map[ch] == 3 ? dp3[len] : dp4[len];
    }

    public static void main(String[] args) {
        统计打字方案数 solution = new 统计打字方案数();
        System.out.println(solution.countTexts("444479999555588866"));
    }
}
